package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 覃国强
 * @date 2022-06-09 18:27
 */
public class 题库_0101_对称二叉树 {

  static
  class Solution {
    public boolean isSymmetric(TreeNode root) {
      if (root == null || (root.left == null && root.right == null)) {
        return true;
      }

      if (root.left == null || root.right == null || root.left.val != root.right.val) {
        return false;
      }

      Deque<TreeNode> pre = new LinkedList<>();
      pre.addFirst(root.left);
      pre.addLast(root.right);

      Deque<TreeNode> next = new LinkedList<>();

      while (!pre.isEmpty()) {
        while (!pre.isEmpty()) {
          TreeNode p = pre.removeFirst();
          TreeNode q = pre.removeLast();
          if (p == null && q == null) {
            continue;
          }
          if (p == null || q == null || p.val != q.val) {
            return false;
          }
          next.addFirst(p.left);
          next.addFirst(p.right);
          next.addLast(q.right);
          next.addLast(q.left);
        }
        Deque<TreeNode> temp = pre;
        pre = next;
        next = temp;
      }
      return true;
    }

    public boolean isSymmetric1(TreeNode root) {
      return helper(root, root);
    }

    private boolean helper(TreeNode p, TreeNode q) {
      if (p == null && q == null) {
        return true;
      }
      if (p == null || q == null) {
        return false;
      }
      return p.val == q.val && helper(p.right, q.left) && helper(p.left, q.right);
    }
  }

}
